home *** CD-ROM | disk | FTP | other *** search
/ C/C++ Users Group Library 1996 July / C-C++ Users Group Library July 1996.iso / listings / v_09_02 / 9n02076a < prev    next >
Text File  |  1990-12-16  |  34KB  |  1,056 lines
  1.  
  2. /*
  3.  *    10-Oct-1990 - created
  4.  */
  5.  
  6. /******************************************************
  7.  *
  8.  *    Module:   olist.c
  9.  *
  10.  *    Purpose:  Functions to manage ordered lists using
  11.  *              skip lists.
  12.  *
  13.  *    (c) Copyright 1990 Kenneth L. Grogan, Jr.
  14.  *
  15.  *    You have permission to use this code for personal,
  16.  *    non-commercial purposes only. Any other use of this
  17.  *    code is prohibitted without the expressed written
  18.  *    consent of Kenneth L. Grogan, Jr.
  19.  *
  20.  ******************************************************/
  21.  
  22.                        /* don't include externals */
  23. #define OLIST_X
  24.  
  25. #include "local.h"
  26. #include "olist.h"
  27. #include "_olist.h"
  28.  
  29.                            /* random level factor p */
  30. #define P_FACTOR        0.25
  31. #define P_LEVEL         (P_FACTOR * RAND_MAX)
  32.                            /* 8 levels will accomodate */
  33.                            /* 65536 items per list */
  34.                            /* for P_FACTOR = .25 */
  35. #define MAX_LEVEL       8
  36.  
  37. #define this    ((SKIPLIST_T *)skip_list)
  38.  
  39. #define OLIST_IS_INVALID(sl)    ((sl) == NULL)
  40.                            /* get appropriate nil node */
  41. #define NIL(sl)         (nil_node[(sl)->key_type])
  42.  
  43.                            /* skip list node */
  44. struct sl_node
  45. {
  46.                            /* array of ptrs to nodes */
  47.     struct sl_node      **next;
  48.     SL_KEY              key;
  49.     void                *client_data;
  50. };
  51. typedef struct sl_node  SL_NODE;
  52.                            /* skip list level */
  53. typedef ubyte   SL_LEVEL;
  54.                            /* skip list */
  55. typedef struct
  56. {
  57.     SL_NODE     *header;
  58.     SL_NODE     *current;
  59.     size_t      size;
  60.     OLIST_KEY_T key_type;
  61.     SL_LEVEL    highest_level;
  62.     int         (*compare_func)();
  63. } SKIPLIST_T;
  64.                            /* maximum key values */
  65. static SL_KEY   max_key_value[OLIST_NUM_KEY_TYPES];
  66.                            /* nil pointers by key */
  67. static SL_NODE  *nil_node[OLIST_NUM_KEY_TYPES];
  68.  
  69.                            /* global error flag */
  70. int     olist_errno;
  71.  
  72.                            /* static prototypes */
  73. #include "__olist.h"
  74.  
  75. /*********************************************************
  76.  *  olist_new: 
  77.  *
  78.  *  Create a new skip list. The new list will contain no
  79.  *      nodes except the header node.
  80.  *
  81.  *  Returns a pointer to the new list, or NULL if an
  82.  *  error occurs.
  83.  *********************************************************/
  84.  
  85. OLIST olist_new (key_type, compare_func)
  86.     OLIST_KEY_T key_type;
  87.     int         (*compare_func)();
  88. {
  89.     register index_t    ii;
  90.     OLIST               skip_list;
  91.     SL_KEY              header_key;
  92.     SL_NODE             *header;
  93.  
  94.     static bool first_time = TRUE;
  95.  
  96.                            /* initialize */
  97.     if (first_time)
  98.     {
  99.         first_time = FALSE;
  100.         SET_MAXIMUM_KEY_VALUES();
  101.         if ( ! olist_make_nil_nodes())
  102.         {
  103.             olist_errno = OLIST_NO_MEMORY;
  104.             return (NULL);
  105.         }
  106.                          /* seed random generator */
  107.         RANDOMIZE();
  108.     }
  109.                            /* check key argument */
  110.     if ((key_type >= MIN_KEY) && (key_type <= MAX_KEY))
  111.     {
  112.                            /* make the list header node */
  113.         header = olist_make_node(MAX_LEVEL, header_key, NULL);
  114.         if (header != NULL)
  115.         {
  116.                            /* make the new skip list */
  117.             skip_list = (OLIST)malloc(sizeof(SKIPLIST_T));
  118.             if (skip_list != NULL)
  119.             {
  120.                 this->header = header;
  121.                 this->key_type = key_type;
  122.                 this->compare_func = compare_func;
  123.                            /* the list starts empty */
  124.                 olist_empty(skip_list);
  125.                            /* return the new skip list */
  126.                 olist_errno = OLIST_SUCCESS;
  127.                 return (skip_list);
  128.             }
  129.             else
  130.             {
  131.                 free(header);
  132.                 olist_errno = OLIST_NO_MEMORY;
  133.             }
  134.         }
  135.         else
  136.         {
  137.             olist_errno = OLIST_NO_MEMORY;
  138.         }
  139.     }
  140.     else
  141.     {
  142.                            /* invalid key type */
  143.         olist_errno = OLIST_INVALID_TYPE;
  144.     }
  145.     return (NULL);
  146. }
  147.  
  148. /***********************************************************
  149.  *  olist_kill:
  150.  *
  151.  *  Destroy the specified skip list by freeing all of its
  152.  *  associated memory.
  153.  *
  154.  *  Returns TRUE if successful, otherwise FALSE.
  155.  **********************************************************/
  156.  
  157. bool olist_kill (skip_list)
  158.     OLIST       skip_list;
  159. {
  160.  
  161.     olist_errno = OLIST_SUCCESS;
  162.                            /* check for valid skip list */
  163.     if (OLIST_IS_INVALID(this))
  164.     {
  165.         olist_errno = OLIST_INVALID;
  166.         return (FALSE);
  167.     }
  168.                            /* free each skip list nodes */
  169.     olist_free_all(skip_list);
  170.                            /* free the list header */
  171.     free(this->header->next);
  172.     free(this->header);
  173.                            /* prevent further access */
  174.     this->key_type = OLIST_NO_KEY;
  175.                            /* free the skip list */
  176.     free(this);
  177.                            /* skip list has been killed */
  178.     return (TRUE);
  179. }
  180.  
  181. /***********************************************************
  182.  *  olist_size:
  183.  *    Return the number of nodes in the specified skip list.
  184.  **********************************************************/
  185.  
  186. size_t olist_size (skip_list)
  187.     OLIST       skip_list;
  188. {
  189.  
  190.     olist_errno = OLIST_SUCCESS;
  191.                            /* check for valid skip list */
  192.     if (OLIST_IS_INVALID(this))
  193.     {
  194.         olist_errno = OLIST_INVALID;
  195.         return (NULL);
  196.     }
  197.                            /* return the list size */
  198.     return (this->size);
  199. }
  200.  
  201. /***********************************************************
  202.  *  olist_key_type:
  203.  *  Return the key type for the specified skip list.
  204.  **********************************************************/
  205.  
  206. OLIST_KEY_T olist_key_type (skip_list)
  207.     OLIST       skip_list;
  208. {
  209.  
  210.     olist_errno = OLIST_SUCCESS;
  211.                            /* check for valid skip list */
  212.     if (OLIST_IS_INVALID(this))
  213.     {
  214.         olist_errno = OLIST_INVALID;
  215.         return (OLIST_NO_KEY);
  216.     }
  217.                            /* return the list key type */
  218.     return (this->key_type);
  219. }
  220.  
  221. /***********************************************************
  222.  *  olist_add:
  223.  *
  224.  *  Add the specified client data to the specified skip list.
  225.  *  The argument replace_data has the following effect:
  226.  *
  227.  *  value  |   key already in the list   |  key not in the list
  228.  *  -----------------------------------------------------------
  229.  *  TRUE   | replace client data for key |  add key to the list
  230.  *  FALSE  |   return KEY_EXISTS error   |  add key to the list
  231.  *
  232.  *  Returns TRUE if the data was inserted or replaced,
  233.  *  otherwise FALSE.
  234.  **********************************************************/
  235.  
  236. bool olist_add (skip_list, key_type, inkey, client_data,
  237.                                replace_data)
  238.     OLIST       skip_list;
  239.     OLIST_KEY_T key_type;
  240.     void        *inkey;
  241.     void        *client_data;
  242.     bool        replace_data;
  243. {
  244.     register index_t    ii;
  245.     SL_LEVEL            new_level;
  246.     SL_KEY              search_key;
  247.     SL_NODE             *new_node;
  248.     SL_NODE             *update_node[MAX_LEVEL];
  249.  
  250.  
  251.     olist_errno = OLIST_SUCCESS;
  252.                            /* check for valid skip list */
  253.     if (OLIST_IS_INVALID(this) ||
  254.         (KEY_IS_INVALID(this, key_type, inkey)))
  255.     {
  256.         olist_errno = OLIST_INVALID;
  257.         return (FALSE);
  258.     }
  259.                            /* get the appropriate key */
  260.     GET_KEY(search_key, key_type, inkey);
  261.                            /* start with the highest */
  262.                            /* level in the header node */
  263.     new_node = this->header;
  264.     ii = this->highest_level + 1;
  265.     do {
  266.         --ii;
  267.                            /* get key before search key */
  268.         while (KEY_LT(this, new_node